package JZ_Offer.dataStructure.list;

import base.ListNode;

/**
 * 链表中倒数最后k个结点
 * <p>
 * 输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
 * 如果该链表长度小于k，请返回一个长度为 0 的链表。
 *
 * @Author piper
 * @Date 2019/12/3 6:16 下午
 */
public class JZ22_链表中倒数最后k个结点 {

    /**
     * 快慢指针
     * 快指针先往前走k步
     * 然后快慢一起往前走 直到链表末尾
     * 这时慢指针 指向的就是倒数第k个节点
     */
    private static ListNode findKthToTail(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        int i = 1;
        while (i < k && fast.next != null) {
            fast = fast.next;
            i++;
        }
        if (i != k) {
            return null;
        }

        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        System.out.println(findKthToTail(a, 6).val);
    }
}
